package 力扣.数组.哈希法;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class 公平的糖果交换888 {
    public static void main(String[] args) {
//        int[] ints1 = {2, 8};
//        int[] ints2 = {0, 6};
        int[] ints1 = {1, 2, 5};
        int[] ints2 = {2, 4};
//        int[] ints1 = {1};
//        int[] ints2 = {6};
        int[] ints = fairCandySwap2(ints1, ints2);
        System.out.println(Arrays.toString(ints));
    }
    public static int[] fairCandySwap(int[] A, int[] B) {
        int sum1 = 0;
        int sum2 = 0;
        int [] re = new int[2];
        for (int te : A){
              sum1 += te;
          }
        for (int te : B){
              sum2 += te;
          }
     // sum1 和 sum2 的大小不知道，所以设置 flag 来判断sum1 和 sum2 的大小
        //其实也不用考虑 sum1 和 sum2 的大小（这里有点多余），仔细想想原因，很简单~
        int flag = 0;
        int de = 0;
        if (sum1 > sum2){
            de = sum1 - sum2;
            de /=2;
            flag = 1;//A > B
        }else{
            de = sum2 - sum1;
            de /=2;
            flag = 2; // A < B
        }

        HashSet<Integer> integers = new HashSet<>();
        for (int i = 0; i < A.length; i++) {
            int te1 = A[i];
 //           使用双重 for 时间复杂度为 O（n²）
            for (int j = 0; j < B.length; j++) {
                int te2 = B[j];
                if (flag == 1){//判断flag(其实不用flag也行)
                    if ( (te1 - te2) == de){//相等则得到答案
                        re[0] = te1;
                        re[1] = te2;
                    }
                }else {
                    if ( (te2 - te1) == de){//相等则得到答案
                        re[0] = te1;
                        re[1] = te2;
                    }
                }
            }

        }
        return re;
    }
    public static int[] fairCandySwap2(int[] A, int[] B) {
        int sumA = Arrays.stream(A).sum();
        int sumB = Arrays.stream(B).sum();
        //其实不用考虑 sum1 和 sum2 的大小  仔细想想
        int delta = (sumA - sumB) / 2;
        Set<Integer> rec = new HashSet<Integer>();
        for (int num : A) {
            rec.add(num);
        }
        int[] ans = new int[2];
        /*   本质就是寻找两个子元素，其差值等于de,差值固定，那么使用一个元素就行了（即只用查找一个元素）。
             使用哈希表来查找就行了*/
        for (int y : B) {
            int x = y + delta;
            if (rec.contains(x)) {
                ans[0] = x;
                ans[1] = y;
                break;
            }
        }
        return ans;
    }

}
